skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Agrawal, Akanksha"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ; ; (, Society for Industrial and Applied Mathematics)
    Full Text Available 
  2. ; ; ; ; (, ACM Transactions on Algorithms)
    Given a graphGand an integerk, theInterval Vertex Deletion (IVD)problem asks whether there exists a subsetS⊆V(G) of size at mostksuch thatG-Sis an interval graph. This problem is known to beNP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed thatIVDis fixed parameter tractable: they exhibited an algorithm with running time 10knO(1). The existence of a polynomial kernel forIVDremained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative. 
    more » « less
    Full Text Available 
  3. ; ; ; ; (, Journal of Graph Theory)
    Abstract A class of graphs admits the Erdős–Pósa property if for any graph , either has vertex‐disjoint “copies” of the graphs in , or there is a set of vertices that intersects all copies of the graphs in . For any graph class , it is natural to ask whether the family of obstructions to has the Erdős–Pósa property. In this paper, we prove that the family of obstructions to interval graphs—namely, the family of chordless cycles and asteroidal witnesses (AWs)—admits the Erdős–Pósa property. In turn, this yields an algorithm to decide whether a given graph has vertex‐disjoint AWs and chordless cycles, or there exists a set of vertices in that hits all AWs and chordless cycles. 
    more » « less
    Full Text Available 
  4. ; ; ; ; ; ; ; ; ; ; et al (, Nature Communications)
    Full Text Available